//463.岛屿的周长
//https://leetcode.cn/problems/island-perimeter/
class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
        int m = grid.size(),n = grid[0].size();
        vector<vector<bool>> check(m,vector<bool>(n,true));

        queue<pair<int,int>> pq;
        for(int i = 0;i<m && pq.empty();++i)
            for(int k = 0;k<n;++k) 
                if(grid[i][k] == 1) 
                {
                    pq.push({i,k});
                    check[i][k] = false;
                    break;
                }
        int ret = 0;
        while(!pq.empty())
        {
            for(int i = 0;i<4;++i)
            {
                int px = pq.front().first + dx[i],py = pq.front().second + dy[i];
                if(px<m&&px>=0&&py<n&&py>=0&&grid[px][py]==1&&check[px][py]) 
                {
                    pq.push({px,py});
                    check[px][py] = false;
                }
                else if(px>=m || px<0 || py>=n || py<0 || check[px][py]) ++ret;
            }
            pq.pop();
        }
        return ret;
    }
};